import java.util.*;

public class Solution417 {
    public List<List<Integer>> pacificAtlantic(int[][] heights) {
        int[] dx=new int[]{0,1,0,-1};
        int[] dy=new int[]{1,0,-1,0};
        Set<List<Integer>> set=new HashSet<>();
        int m=heights.length,n=heights[0].length;
        boolean[][] visit=new boolean[m][n];
        Queue<int[]> queue=new LinkedList<>();
        for (int i=0;i<m;i++){
            visit[i][0]=true;
            queue.offer(new int[]{i,0});
            set.add(Arrays.asList(i,0));
        }
        for (int i=1;i<n;i++){
            visit[0][i]=true;
            queue.offer(new int[]{0,i});
            set.add(Arrays.asList(0,i));
        }
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            for (int i=0;i<4;i++){
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && !visit[x][y] && heights[x][y]>=heights[t[0]][t[1]]){
                    visit[x][y]=true;
                    queue.offer(new int[]{x,y});
                    set.add(Arrays.asList(x,y));
                }
            }
        }
        for (boolean[] booleans : visit) {
            Arrays.fill(booleans,false);
        }
        List<List<Integer>> ans=new ArrayList<>();
        for (int i=0;i<m;i++){
            visit[i][n-1]=true;
            queue.offer(new int[]{i,n-1});
            if (set.contains(Arrays.asList(i,n-1))){
                ans.add(Arrays.asList(i,n-1));
            }
        }
        for (int i=0;i<n-1;i++){
            visit[m-1][i]=true;
            queue.offer(new int[]{m-1,i});
            if (set.contains(Arrays.asList(m-1,i))){
                ans.add(Arrays.asList(m-1,i));
            }
        }
        while (!queue.isEmpty()){
            int[] t=queue.poll();
            for (int i=0;i<4;i++){
                int x=t[0]+dx[i];
                int y=t[1]+dy[i];
                if (x>=0 && x<m && y>=0 && y<n && !visit[x][y] && heights[x][y]>=heights[t[0]][t[1]]){
                    visit[x][y]=true;
                    queue.offer(new int[]{x,y});
                    if (set.contains(Arrays.asList(x,y))){
                        ans.add(Arrays.asList(x,y));
                    }
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution417().pacificAtlantic(new int[][]{{1,2,2,3,5},{3,2,3,4,4},{2,4,5,3,1},{6,7,1,4,5},{5,1,1,2,4}}));
    }
}
